package leetCode.hw.math;

/**
 * 棋盘走到对角的方式
 */
public class HJ91Solution implements HJ91{


    /**
     * 递归解法
     * @param n
     * @param m
     * @return
     */
    @Override
    public int walkWays(int n, int m) {
        return calSub(n,m);
    }

    /**
     * 递归解法
     * @param x
     * @param y
     * @return
     */
    public static int calSub(int x,int y) {
        if(x==1&&y==1) return 2;
        if(x==1) return calSub(x,y-1)+1;
        if(y==1) return calSub(x-1,y)+1;
        return calSub(x-1,y)+calSub(x,y-1);
    }

    /**
     * 动态规划解法
     * @param n
     * @param m
     * @return
     */
    public static int dpSolution(int n,int m) {
        int[][] dp = new int[n+1][m+1];
        for(int i=1;i<=n;i++){
            dp[i][1] = i+1;
        }
        for(int i=1;i<=m;i++){
            dp[1][i] = i+1;
        }
        for(int i=2;i<=n;i++) {
            for(int j=2;j<=m;j++) {
                dp[i][j] = dp[i-1][j] + dp[i][j-1];
            }
        }
        return dp[n][m];
    }





}


